module ecs {
    /**
     * 性能优化的位集实现。这些方法不执行任何验证，主要用于在内部优化对entityId位集的访问
     */
    export class BitVector{
        private _words: number[] = [0];

        /**
         * 创建一个比特集，其初始大小足够大，可以显式地表示索引在0到nbit -1范围内的比特。
         * @param nbits 位集的初始大小
         */
        constructor(nbits?: number){
            if (nbits != undefined)
                this.checkCapacity(nbits.rightMove(6));
        }

        /**
         * 
         * @param index 索引位的索引
         */
        public get(index: number): boolean {
            let word = index.rightMove(6);
            return word < this._words.length && (this._words[word] & (1 << index)) != 0;
        }

        /**
         * 
         * @param index 索引要设置的位的索引
         */
        public set(index: number, value: boolean = true){
            if (value){
                let word = index.rightMove(6);
                this.checkCapacity(word);
                this._words[word] |= 1 << index;
            }else{
                this.clear(index);
            }
        }

        /**
         * 
         * @param index 
         */
        public unsafeGet(index: number){
            return (this._words[index.rightMove(6)] & (1 << index)) != 0;
        }

        /**
         * 
         * @param index 
         */
        public unsafeSet(index: number, value: boolean = true){
            if (value){
                this._words[index.rightMove(6)] |= 1 << index;
            } else{
                this.unsafeClear(index);
            }
        }

        /**
         * 
         * @param index 
         */
        public unsafeClear(index: number){
            this._words[index.rightMove(6)] &= ~(1 << index);
        }

        /**
         * 
         * @param index 要清除索引的索引位
         */
        public clear(index?: number){
            if (index == undefined){
                let word = index.rightMove(6);
                if (word >= this._words.length) return;
                this._words[word] &= ~(1 << index);
            }else{
                for (let i = 0; i < this._words.length; i++) {
                    this._words[i] = 0;
                }
            }
        }

        /**
         * 返回这个位集的“逻辑大小”:位集中最高位的索引加1。如果位集不包含集合位，则返回零
         */
        public length(): number{
            let bits = this._words;
            for (let word = bits.length; word >= 0; --word) {
                let bitsAtWord = bits[word];
                if (bitsAtWord != 0)
                    return (word << 6) + 64 - this.numberOfLeadingZeros(bitsAtWord);
            }

            return 0;
        }

        /**
         * 如果该位集不包含设置为true的位，则返回true
         */
        public isEmpty(): boolean{
            let bits = this._words;
            let length = bits.length;
            for (let i = 0; i < length; i ++){
                if (bits[i] != 0)
                    return false;
            }

            return true;
        }

        public toIntBag(out: NumberBag): NumberBag{
            if (this.isEmpty()){
                out.setSize(0);
                return out;
            }

            let count = this.prepareBag(out, 2);
            let data = out.getData();
            for (let i = 0, index = 0; count > index; i++){
                let bitset = this._words[i];
                let wordBits = i << 6;
                while (bitset != 0){
                    let t = bitset & -bitset;
                    data[index] = wordBits + this.bitCount(t - 1);
                    bitset ^= t;

                    index ++;
                }
            }

            return out;
        }

        public toIntBagIdCid(cm: ComponentManager, out: NumberBag): NumberBag{
            if (this.isEmpty()){
                out.setSize(0)
                return out;
            }

            let count = this.prepareBag(out, 2);
            let data = out.getData();
            for (let i = 0, index = 0; count > index; i++){
                let bitset = this._words[i];
                let wordBits = i << 6;
                while (bitset != 0){
                    let t = bitset & -bitset;
                    let id = wordBits + this.bitCount(t - 1);
                    data[index] = id;
                    data[index + 1] = cm.getIdentity(id);
                    index += 2;
                    bitset ^= t;
                }
            }

            return out;
        }

        private prepareBag(out: NumberBag, elementsPerEntry){
            let count = elementsPerEntry * this.cardinality();
            out.ensureCapacity(count);
            out.setSize(count);
            return count;
        }

        public cardinality(): number{
            let count = 0;
            for (let i = 0; i < this._words.length; i ++){
                count += this.bitCount(this._words[i]);
            }

            return count;
        }

        private bitCount(i: number): number{
            i = i - (i.rightMove(1) & 0x5555555);
            i = (i & 0x33333333) + ((i.rightMove(2) & 0x33333333));
            i = (i + (i.rightMove(4))) & 0x0f0f0f0f;
            i = i + i.rightMove(8);
            i = i + i.rightMove(16);
            return i & 0x3f;
        }

        private numberOfLeadingZeros(i: number){
            if (i == 0)
                return 32;
            let n = 1;
            if (i.rightMove(16) == 0){
                n += 16;
                i <<= 16;
            }

            if (i.rightMove(24) == 0){
                n += 8;
                i <<= 8;
            }

            if (i.rightMove(28) == 0){
                n += 4;
                i <<= 4;
            }

            if (i.rightMove(30) == 0){
                n += 2;
                i <<= 2;
            }

            n -= i.rightMove(31);
            return n;
        }

        /**
         * 增长后端数组(long[])，以便它可以保存请求的位。主要适用于依赖于不安全的方法，包括{@link #unsafeGet(int)}和{@link #unsafeClear(int)}。
         * @param bits 
         */
        public ensureCapacity(bits: number){
            this.checkCapacity(bits.rightMove(6));
        }

        private checkCapacity(len: number){
            if (len >= this._words.length){
                let newBits = new Number[len + 1];
                this._words.copy(0, newBits, 0, this._words.length);
                this._words = newBits;
            }
        }
    }
}
